package com.dataStructures.linkedlist;

import lombok.Getter;
import lombok.Setter;

import java.util.Stack;

/**
 * 单向链表
 */
public class SingleLinkedListDemo {
	public static void main(String[] args) {
		HeroNode heroNode1 = new HeroNode(1, "zhangsan", "zs");
		HeroNode heroNode2 = new HeroNode(2, "lisi", "ls");
		HeroNode heroNode3 = new HeroNode(3, "wangwu", "ww");
		HeroNode heroNode4 = new HeroNode(4, "zhaoliu", "zl");

		SingleLinkedList singleLinkedList = new SingleLinkedList();
		singleLinkedList.addByOrder(heroNode1);
		singleLinkedList.addByOrder(heroNode4);
		singleLinkedList.addByOrder(heroNode2);
		singleLinkedList.addByOrder(heroNode3);

		singleLinkedList.list();
		System.out.println("长度为：" + singleLinkedList.getLength(singleLinkedList.getHead()));
		System.out.println("========逆序打印===========");
		singleLinkedList.reversePrint(singleLinkedList.getHead());

		System.out.println("========反转后===========");
		singleLinkedList.reverseList(singleLinkedList.getHead());
		singleLinkedList.list();

		System.out.println("===================");

		singleLinkedList.del(1);
		singleLinkedList.del(4);
		System.out.println("================");
		singleLinkedList.list();

		singleLinkedList.update(new HeroNode(2, "yanqi", "yq"));
		System.out.println("================");
		singleLinkedList.list();
	}
}

class SingleLinkedList {
	/**
	 * 初始化一个头节点，不存放具体数据
	 */
	private final HeroNode head = new HeroNode(0, "", "");

	public HeroNode getHead() {
		return head;
	}

	/**
	 * 添加节点到单向链表
	 * 1. 找到当前链表的最后节点
	 * 2. 将最后这个节点的 next 指向 新的节点
	 */
	public void add(HeroNode node) {
		// 因为 head 节点不能动，因此我们需要一个辅助遍历 temp
		HeroNode temp = head;
		while (true) {
			if (temp.next == null) {
				break;
			}
			temp = temp.next;
		}
		temp.next = node;
	}

	/**
	 * 按照 no 顺序添加
	 */
	public void addByOrder(HeroNode node) {
		HeroNode temp = head;
		// 添加编号是否存在
		boolean flag = false;
		while (true) {
			// 在链表的最后添加
			if (temp.next == null) {
				break;
			}
			// 在 temp 位置后边添加
			if (temp.next.no > node.no) {
				break;
			}
			// 编号存在
			if (temp.next.no == node.no) {
				flag = true;
				break;
			}
			temp = temp.next;
		}
		if (flag) {
			System.out.printf("编号 %d 已经存在" + node.no);
		} else {
			node.next = temp.next;
			temp.next = node;
		}
	}

	/**
	 * 根据 no 来修改
	 *
	 * @param node
	 */
	public void update(HeroNode node) {
		if (head.next == null) {
			System.out.println("链表为空");
			return;
		}
		HeroNode temp = head.next;
		// 是否找到目标节点
		boolean flag = false;
		while (true) {
			if (temp == null) {
				return;
			}
			if (temp.no == node.no) {
				flag = true;
				break;
			}
			temp = temp.next;
		}

		if (flag) {
			temp.name = node.name;
			temp.nickName = node.nickName;
		} else {
			System.out.printf("没有找到编号 %d 的节点", node.no);
		}
	}

	public void del(int no) {
		HeroNode temp = head;
		boolean flag = false;
		while (true) {
			if (temp.next == null) {
				break;
			}
			if (temp.next.no == no) {
				flag = true;
				break;
			}
			temp = temp.next;
		}
		if (flag) {
			temp.next = temp.next.next;
		} else {
			System.out.printf("要删除的节点 %d 不存在", no);
		}
	}

	public void list() {
		if (head.next == null) {
			System.out.println("链表为空");
			return;
		}
		HeroNode temp = head.next;
		while (true) {
			if (temp == null) {
				break;
			}
			System.out.println(temp);
			temp = temp.next;
		}
	}

	public int getLength(HeroNode head) {
		if (head.next == null) {
			return 0;
		}
		int length = 0;
		HeroNode temp = head.next;
		while (temp != null) {
			length++;
			temp = temp.next;
		}
		return length;
	}

	/**
	 * 查找单链表中的倒数第 k 个结点 【新浪面试题】
	 * 思路
	 * 1. 编写一个方法，接收 head 节点，同时接收一个 index
	 * 2. index 表示是倒数第 index 个节点
	 * 3. 先把链表从头到尾遍历，得到链表的总的长度 getLength
	 * 4. 得到 size 后，我们从链表的第一个开始遍历 (size-index)个，就可以得到
	 * 5. 如果找到了，则返回该节点，否则返回 nulll
	 */
	public HeroNode findLastIndexNode(HeroNode head, int index) {
		// 判断如果链表为空，返回 null
		if (head.next == null) {
			return null;
		}
		// 第一个遍历得到链表的长度(节点个数)
		int size = getLength(head);
		// 第二次遍历 size-index 位置，就是我们倒数的第 K 个节点
		// 先做一个 index 的校验
		if (index <= 0 || index > size) {
			return null;
		}
		// 定义给辅助变量，for 循环定位到倒数的 index
		// //3 // 3 - 1 = 2
		HeroNode cur = head.next;
		for (int i = 0; i < size - index; i++) {
			cur = cur.next;
		}
		return cur;
	}

	/**
	 * 反转链表【腾讯面试题】
	 */
	public void reverseList(HeroNode head) {
		// 如果当前链表为空或只有一个节点，直接返回
		if (head.next == null || head.next.next == null) {
			return;
		}
		HeroNode cur = head.next;
		HeroNode next;
		HeroNode reverseHead = new HeroNode(0, "", "");

		// 遍历原来的链表，每遍历一个节点，就将其取出，并放在新的链表 reverseHead 的最前端
		while (cur != null) {
			// 先暂时保存当前节点的下一个节点，因为后面需要使用
			next = cur.next;
			// 将 cur 的下一个节点指向新的链表的最前端
			cur.next = reverseHead.next;
			// 将 cur 连接到新的链表上
			reverseHead.next = cur;
			// 让 cur 后移
			cur = next;
		}
		// 将 head.next 指向 reverseHead.next , 实现单链表的反转
		head.next = reverseHead.next;
	}

	/**
	 * 单链表的逆序打印【百度】
	 * 思路：利用栈先进后出的特性来实现
	 */
	public void reversePrint(HeroNode head) {
		if (head.next == null) {
			return;
		}
		Stack<HeroNode> stack = new Stack();
		HeroNode cur = head.next;
		while (cur != null) {
			stack.push(cur);
			cur = cur.next;
		}

		while (stack.size() > 0) {
			System.out.println(stack.pop());
		}
	}

}

@Getter
@Setter
class HeroNode {
	public int no;
	public String name;
	public String nickName;
	public HeroNode next;

	public HeroNode(int no, String name, String nickName) {
		this.no = no;
		this.name = name;
		this.nickName = nickName;
	}

	@Override
	public String toString() {
		final StringBuffer sb = new StringBuffer("HeroNode{");
		sb.append("no=").append(no);
		sb.append(", name='").append(name).append('\'');
		sb.append(", nickName='").append(nickName).append('\'');
		sb.append('}');
		return sb.toString();
	}
}